package offer.easy.math;

public class JumpFloor {

    //青蛙一次可以跳[1,n]步，则在青蛙跳到最后一次之前可以在[1,n-1]的任意台阶
    //设青蛙跳N级台阶的跳法共有f(n)种
    //f(n) = f(n-1) + f(n-2) + ...... + f(1)
    //f(n-1) = f(n-2) + f(n-3) + ...... + f(1)
    //相减：f(n) = 2f(n-1)，推出f(n) = 2*(n-1)

    public static int JumpFloorI(int target) {
        if(target > 2) {
            //(int)Math.pow(2,(target-1));
            return 1<<(target-1);
        } else {
            return target;
        }
    }

    public static int JumpFloorII(int target) {
        int[] stepArray = new int[target+1];
        int sum = 0;
        if (target <= 2) {
            sum = target;
        } else {
            stepArray[0] = 0;
            stepArray[1] = 1;
            stepArray[2] = 2;
            for (int i = 3; i <= target; i++) {
                sum = 0;
                for (int j = 1; j < i; j++) {
                    sum = sum + stepArray[j];
                }
                stepArray[i] = sum + 1;
            }
        }
        sum = stepArray[target];
        return sum;
    }

    public static void main(String[] args) {
        int re = JumpFloorII(10);
        System.out.println(re);
    }
}
